package dynamic;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author luo
 * @description
 * @since 2022/7/20 17:29
 */
public class GenerateParenthesis {

    String[][] cache;

    public static void main(String[] args) {
        new GenerateParenthesis().generateParenthesis(3).forEach(System.out::println);
    }


    public List<String> generateParenthesis(int n) {
        cache = new String[n][];
        return Arrays.stream(calculate(n-1)).distinct().collect(Collectors.toList());
       /* return Arrays.stream(cache[n-1]).filter(Objects::nonNull)
//                .flatMap(Arrays::stream)
                .distinct()
                .collect(Collectors.toList());*/
    }


    private String[] calculate(int n) {
        if (n <= 0) {
            return new String[]{"()"};
        }
        String[] cacheResult = cache[n];
        if (cacheResult != null) {
            System.out.println("缓存命中：" + Arrays.toString(cacheResult));
            return cacheResult;
        }

        String[] middle = calculate(n - 1);
        return cache[n] = Arrays.stream(middle).flatMap(element -> {
            return Stream.of(
                    String.format("(%s)", element),
                    String.format("()%s", element),
                    String.format("%s()", element)
            );
        }).toArray(String[]::new);


    }
}
